#ifndef CAMPUS_GRAPH_H
#define CAMPUS_GRAPH_H

#include <fstream>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

class CampusGraph {
private:
  int numVertices;
  vector<string> vertices;
  vector<vector<int> > nextVertex; // Floyd
  vector<vector<int> > adjacencyMatrix;
  map<string, int> vertexIndex;

  void initializeFloyd();
  void floydWarshall();
  int dpTSP(int pos, int visited, vector<vector<int> > &dp,
            vector<vector<int> > &parent, const vector<int> &validVertices);

public:
  CampusGraph() : numVertices(0) {}

  bool loadFromFile(const string &filename);
  void showVertices();
  pair<vector<string>, int> findShortestPath(const string &start,
                                             const string &end);
  vector<pair<vector<string>, int> > findTourPaths(const string &entrance,
                                                  int maxPaths = 5);
  void showPath(const pair<vector<string>, int> &path);
  string getVertexName(int index);

private:
  bool isEulerian(const vector<int>& validVertices);
  void findTourPathsHelper(vector<pair<vector<string>, int> > &allPaths,
                           vector<string> &currentPath, vector<bool> &visited,
                           const string &current, const string &entrance,
                           int &pathLength, int maxPaths);
  vector<string> findIsolatedVertices(const string &entrance);
};

#endif
